package src.com.syx.linkedList;

/**
 * @author 邵一鑫
 * @date 2025/6/18 10:32
 */
public class SingleLinkedListDemo {
    public static void main(String[] args) {
// 创建单链表实例
        SingleLinkedList<String> list = new SingleLinkedList<>();

        System.out.println("=== 测试单链表功能 ===");

        // 1. 测试添加功能
        System.out.println("\n1. 测试添加功能:");
        list.addFirst("First");
        list.addLast("Last");
        list.add(1, "Middle");
        System.out.println("链表内容: " + list); // 预期: [First, Middle, Last]
        System.out.println("当前大小: " + list.size()); // 预期: 3

        // 2. 测试获取功能
        System.out.println("\n2. 测试获取功能:");
        System.out.println("第一个元素: " + list.getFirst()); // 预期: First
        System.out.println("最后一个元素: " + list.getLast()); // 预期: Last
        System.out.println("索引1的元素: " + list.get(1)); // 预期: Middle

        // 3. 测试修改功能
        System.out.println("\n3. 测试修改功能:");
        list.set(1, "Updated");
        System.out.println("修改后的链表: " + list); // 预期: [First, Updated, Last]

        // 4. 测试查找功能
        System.out.println("\n4. 测试查找功能:");
        System.out.println("包含'First'吗? " + list.contains("First")); // 预期: true
        System.out.println("包含'Missing'吗? " + list.contains("Missing")); // 预期: false

        // 5. 测试删除功能
        System.out.println("\n5. 测试删除功能:");
        System.out.println("删除第一个元素: " + list.removeFirst()); // 预期: First
        System.out.println("删除后的链表: " + list); // 预期: [Updated, Last]

        System.out.println("删除最后一个元素: " + list.removeLast()); // 预期: Last
        System.out.println("删除后的链表: " + list); // 预期: [Updated]

        list.addLast("NewLast");
        System.out.println("添加元素后的链表: " + list); // 预期: [Updated, NewLast]

        System.out.println("删除'Updated': " + list.remove("Updated")); // 预期: true
        System.out.println("删除后的链表: " + list); // 预期: [NewLast]

        // 6. 测试边界情况
        System.out.println("\n6. 测试边界情况:");
        try {
            list.get(5); // 预期抛出异常
        } catch (IndexOutOfBoundsException e) {
            System.out.println("捕获到预期异常: " + e.getMessage());
        }

        // 7. 测试清空功能
        System.out.println("\n7. 测试清空功能:");
        list.clear();
        System.out.println("清空后的链表: " + list); // 预期: []
        System.out.println("链表是否为空? " + list.isEmpty()); // 预期: true

        // 8. 测试整数链表
        System.out.println("\n8. 测试整数链表:");
        SingleLinkedList<Integer> intList = new SingleLinkedList<>();
        intList.addLast(10);
        intList.addLast(20);
        intList.addLast(30);
        System.out.println("整数链表: " + intList); // 预期: [10, 20, 30]
        System.out.println("总和: " + (intList.get(0) + intList.get(1) + intList.get(2))); // 预期: 60
    }
}

class SingleLinkedList<T> {
    private static class Node<T> {
        T data;
        Node<T> next;

        Node(T data) {
            this.data = data;
            this.next = null;
        }
    }

    private final Node<T> head; // 头节点不存储数据
    private int size;

    public SingleLinkedList() {
        this.head = new Node<T>(null);
        this.size = 0;
    }

    // 1. 获取链表长度
    public int size() {
        return size;
    }

    // 2. 判断链表是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 3. 在指定索引处添加元素
    public void add(int index, T data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }

        Node<T> prev = head;
        // 找到要插入位置的前一个节点
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        Node<T> node = new Node<>(data);
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    // 4. 在链表头部添加元素
    public void addFirst(T data) {
        add(0, data);
    }

    // 5. 在链表尾部添加元素
    public void addLast(T data) {
        add(size, data);
    }

    // 6. 获取指定位置的元素
    public T get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<T> current = head.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.data;
    }

    // 7. 获取第一个元素
    public T getFirst() {
        if (isEmpty()) {
            throw new RuntimeException("LinkedList is empty");
        }
        return head.next.data;
    }

    // 8. 获取最后一个元素
    public T getLast() {
        if (isEmpty()) {
            throw new RuntimeException("LinkedList is empty");
        }
        return get(size - 1);
    }

    // 9. 修改指定位置的元素
    public void set(int index, T data) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        Node<T> current = head.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        current.data = data;
    }

    // 10. 查找是否包含某元素
    public boolean contains(T data) {
        Node<T> current = head.next;
        while (current != null) {
            if (current.data.equals(data)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    // 11. 删除指定位置的元素
    public T remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }

        Node<T> prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }

        Node<T> nodeToRemove = prev.next;
        prev.next = nodeToRemove.next;
        nodeToRemove.next = null; // help GC
        size--;
        return nodeToRemove.data;
    }

    // 12. 删除第一个元素
    public T removeFirst() {
        if (isEmpty()) {
            throw new RuntimeException("LinkedList is empty");
        }
        return remove(0);
    }

    // 13. 删除最后一个元素
    public T removeLast() {
        if (isEmpty()) {
            throw new RuntimeException("LinkedList is empty");
        }
        return remove(size - 1);
    }

    // 14. 删除指定元素
    public boolean remove(T data) {
        Node<T> prev = head;
        Node<T> current = head.next;

        while (current != null) {
            if (current.data.equals(data)) {
                prev.next = current.next;
                current.next = null; // help GC
                size--;
                return true;
            }
            prev = current;
            current = current.next;
        }
        return false;
    }

    // 15. 清空链表
    public void clear() {
        head.next = null;
        size = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Node<T> current = head.next;
        while (current != null) {
            sb.append(current.data);
            if (current.next != null) {
                sb.append(", ");
            }
            current = current.next;
        }
        sb.append("]");
        return sb.toString();
    }
}